package algorithm_optimal_solution.StackAndQueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

//猫狗队列，创建两个队列一个存放猫一个存放狗，顺序按时间戳比较即可。
public class CatAndDogQueue {

    static class Dog extends Pet{
        public Dog(int number){
            super("dog",number);
        }
    }

    static class Cat extends Pet{
        public Cat(int number){
            super("cat",number);
        }
    }

    static class Pet{
        private String type;
        private int number;
        public Pet(String type,int number){
            this.type = type;
            this.number = number;
        }
        public String getType(){
            return this.type;
        }

        public int getNumber(){
            return this.number;
        }
    }

    static class PetQueue{
        private Pet pet;
        private long count;

        public PetQueue(Pet pet,long count){
            this.pet = pet;
            this.count = count;
        }

        public long getCount(){
            return this.count;
        }

        public String getTypeAndNumber(){
            return this.pet.getType()+ " " +this.pet.getNumber();
        }
    }


    public static Queue<PetQueue> catQueue;
    public static Queue<PetQueue> dogQueue;
    public long count;

    public CatAndDogQueue(){
        catQueue = new LinkedList<>();
        dogQueue = new LinkedList<>();
        count = 0;
    }

    public void add(Pet pet){
        if(pet.getType().equals("cat")){
            catQueue.offer(new PetQueue(pet,this.count++));
        }else if(pet.getType().equals("dog")){
            dogQueue.offer(new PetQueue(pet,this.count++));
        }
    }

    public void pollAll(){
        while(!catQueue.isEmpty() && !dogQueue.isEmpty()){
            System.out.println(catQueue.peek().getCount() < dogQueue.peek().getCount()?
                    catQueue.poll().getTypeAndNumber():
                    dogQueue.poll().getTypeAndNumber());
        }
        while(!catQueue.isEmpty()){
            System.out.println(catQueue.poll().getTypeAndNumber());
        }
        while(!dogQueue.isEmpty()){
            System.out.println(dogQueue.poll().getTypeAndNumber());
        }
    }

    public void pollDog(){
        while(!dogQueue.isEmpty()){
            System.out.println(dogQueue.poll().getTypeAndNumber());
        }
    }

    public void pollCat(){
        while(!catQueue.isEmpty()){
            System.out.println(catQueue.poll().getTypeAndNumber());
        }
    }

    public String isEmpty(){
        return catQueue.isEmpty() && dogQueue.isEmpty()?"yes":"no";
    }

    public String isDogEmpty(){
        return dogQueue.isEmpty()?"yes":"no";
    }

    public String isCatEmpty(){
        return catQueue.isEmpty()?"yes":"no";
    }

    public static void main(String[] args)throws IOException{
        CatAndDogQueue main=new CatAndDogQueue();
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len=Integer.parseInt(scanner.readLine());
        for(int i=0;i<len;i++){
            String value=scanner.readLine();
            if(value.equals("pollAll")){
                main.pollAll();
            }else if(value.equals("pollDog")){
                main.pollDog();
            }else if(value.equals("pollCat")){
                main.pollCat();
            }else if(value.equals("isEmpty")){
                System.out.println(main.isEmpty());
            }else if(value.equals("isDogEmpty")){
                System.out.println(main.isDogEmpty());
            }else if(value.equals("isCatEmpty")){
                System.out.println(main.isCatEmpty());
            }else{
                String[] result=value.split(" ");
                Pet pet;
                if(result[1].equals("cat")){
                    pet=new Cat(Integer.parseInt(result[2]));
                }else{
                    pet=new Dog(Integer.parseInt(result[2]));
                }
                main.add(pet);
            }
        }
    }
}
